/**
 * 
 */
package tree;

import java.util.Stack;

import utils.CreateUtils;

/**
 * @author Michael
 *
 */
public class Traversal {

	public static void preTraverseIterative(Node<Integer> root) {
		if (root == null)
			return;
		Stack<Node<Integer>> stack = new Stack<Node<Integer>>();
		stack.add(root);
		while (!stack.isEmpty()) {
			Node<Integer> node = stack.pop();
			System.out.printf("%d ", node.value);
			if (node.right != null) {
				stack.push(node.right);
			}
			if (node.left != null) {
				stack.push(node.left);
			}
		}
	}

	public static void inTraverseIterative(Node<Integer> root) {
		Stack<Node<Integer>> stack = new Stack<Node<Integer>>();
		Node<Integer> current = root;
		while (!stack.isEmpty() || current != null) {
			if (current != null) {
				stack.push(current);
				current = current.left;
			} else {
				Node<Integer> node = stack.pop();
				System.out.printf("%d ", node.value);
				current = node.right;
			}
		}
	}

	public static void postTraverseIterative(Node<Integer> root) {
		Stack<Node<Integer>> stack = new Stack<Node<Integer>>();
		Node<Integer> current = root;
		while (!stack.isEmpty() || current != null) {
			if (current != null) {
				stack.push(current);
				current = current.left;
			} else {
				while (!stack.isEmpty() && stack.peek().right == current) {
					current = stack.pop();
					System.out.printf("%d ", current.value);
				}
				current = stack.isEmpty() ? null : stack.peek().right;
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		preTraverseIterative(CreateUtils.bstWithTenNodes());
		System.out.println();
		inTraverseIterative(CreateUtils.bstWithTenNodes());
		System.out.println();
		postTraverseIterative(CreateUtils.bstWithTenNodes());
	}

	/**
	 * 
	 */
	public Traversal() {

	}
}
